<!doctype html><html lang=cn-zh><head><meta charset=UTF-8><meta name=viewport content="width=device-width,initial-scale=1"><meta http-equiv=X-UA-Compatible content="IE=edge"><style type=text/css>body{font-family:monospace}</style><title>[算法笔记]使用L形砖拼接国际象棋棋盘</title>
<meta name=description content="A blog maintained by Vimiix."><link rel=stylesheet href=/css/style.css><script>var _hmt=_hmt||[];(function(){var e,t=document.createElement("script");t.src="https://hm.baidu.com/hm.js?7c24231917964240bae97e813810620c",e=document.getElementsByTagName("script")[0],e.parentNode.insertBefore(t,e)})()</script></head><body><header>====================<br>== Hi, I'm Vimiix ==<br>====================<div style=float:right;color:gray;font-size:x-large>Get hands dirty.</div><br><p><nav><a href=https://www.vimiix.com/><b>首页</b></a>.
<a href=/posts/><b>文章列表</b></a>.
<a href=/projects/><b>开源项目</b></a>.
<a href=/tags/><b>标签</b></a>.
<a href=/friends/><b>友链</b></a>.
<a href=/about/><b>关于我</b></a>.
<a href=/index.xml><b>RSS</b></a>.</nav></p></header><main><article><h1>[算法笔记]使用L形砖拼接国际象棋棋盘</h1><b><time>2017.08.01 19:54</time></b>
<a href=/tags/algorithms>algorithms</a>
<a href=/tags/python>Python</a><div><h2 id=递归解决棋盘拼接问题>递归解决棋盘拼接问题</h2><h3 id=题目介绍>题目介绍</h3><p>如图所示，图中有一块角上缺了一个方格的国际象棋棋盘，现在我们想用 L 形砖拼接出这样一块棋盘。</p><p><figure><img src=http://vimiix-blog.oss-cn-qingdao.aliyuncs.com/chess-board.jpg alt></figure></p><h3 id=python-代码>Python 代码</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>def</span> <span style=color:#a6e22e>cover</span>(board, lab<span style=color:#f92672>=</span><span style=color:#ae81ff>1</span>, top<span style=color:#f92672>=</span><span style=color:#ae81ff>0</span>, left<span style=color:#f92672>=</span><span style=color:#ae81ff>0</span>, side<span style=color:#f92672>=</span><span style=color:#66d9ef>None</span>):
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>if</span> side <span style=color:#f92672>is</span> <span style=color:#66d9ef>None</span>:
</span></span><span style=display:flex><span>	    side <span style=color:#f92672>=</span> len(board)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>	  s <span style=color:#f92672>=</span> side <span style=color:#f92672>//</span> <span style=color:#ae81ff>2</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>	  offsets <span style=color:#f92672>=</span> (<span style=color:#ae81ff>0</span>, <span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>), (side<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>, <span style=color:#ae81ff>0</span>)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>for</span> dy_outer, dy_inner <span style=color:#f92672>in</span> offsets:
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>for</span> dx_outer, dx_inner <span style=color:#f92672>in</span> offsets:
</span></span><span style=display:flex><span>	      <span style=color:#66d9ef>if</span> <span style=color:#f92672>not</span> board[top<span style=color:#f92672>+</span>dy_outer][left<span style=color:#f92672>+</span>dx_outer]:
</span></span><span style=display:flex><span>	        board[top<span style=color:#f92672>+</span>s<span style=color:#f92672>+</span>dy_inner][left<span style=color:#f92672>+</span>s<span style=color:#f92672>+</span>dx_inner] <span style=color:#f92672>=</span> lab
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>	lab <span style=color:#f92672>+=</span> <span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>if</span> s <span style=color:#f92672>&gt;</span> <span style=color:#ae81ff>1</span>:
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>for</span> dy <span style=color:#f92672>in</span> [<span style=color:#ae81ff>0</span>, s]:
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>for</span> dx <span style=color:#f92672>in</span> [<span style=color:#ae81ff>0</span>, s]:
</span></span><span style=display:flex><span>	      lab <span style=color:#f92672>=</span> cover(board, lab, top<span style=color:#f92672>+</span>dy, left<span style=color:#f92672>+</span>dx, s)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>return</span> lab
</span></span></code></pre></div><blockquote><p>运行一下代码</p></blockquote><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#f92672>&gt;&gt;&gt;</span> board <span style=color:#f92672>=</span> [[<span style=color:#ae81ff>0</span>]<span style=color:#f92672>*</span><span style=color:#ae81ff>8</span> <span style=color:#66d9ef>for</span> i <span style=color:#f92672>in</span> range(<span style=color:#ae81ff>8</span>)]
</span></span><span style=display:flex><span>	<span style=color:#f92672>&gt;&gt;&gt;</span> board[<span style=color:#ae81ff>0</span>][<span style=color:#ae81ff>7</span>] <span style=color:#f92672>=</span> <span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>	<span style=color:#f92672>&gt;&gt;&gt;</span> cover(board)
</span></span><span style=display:flex><span>	<span style=color:#ae81ff>22</span>
</span></span><span style=display:flex><span>	<span style=color:#f92672>&gt;&gt;&gt;</span> <span style=color:#66d9ef>for</span> row <span style=color:#f92672>in</span> board:
</span></span><span style=display:flex><span>	<span style=color:#f92672>...</span>   print((<span style=color:#e6db74>&#34; </span><span style=color:#e6db74>%2i</span><span style=color:#e6db74>&#34;</span><span style=color:#f92672>*</span><span style=color:#ae81ff>8</span>)<span style=color:#f92672>%</span>tuple(row))
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>	  <span style=color:#ae81ff>3</span>  <span style=color:#ae81ff>3</span>  <span style=color:#ae81ff>4</span>  <span style=color:#ae81ff>4</span>  <span style=color:#ae81ff>8</span>  <span style=color:#ae81ff>8</span>  <span style=color:#ae81ff>9</span> <span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>	  <span style=color:#ae81ff>3</span>  <span style=color:#ae81ff>2</span>  <span style=color:#ae81ff>2</span>  <span style=color:#ae81ff>4</span>  <span style=color:#ae81ff>8</span>  <span style=color:#ae81ff>7</span>  <span style=color:#ae81ff>9</span>  <span style=color:#ae81ff>9</span>
</span></span><span style=display:flex><span>	  <span style=color:#ae81ff>5</span>  <span style=color:#ae81ff>2</span>  <span style=color:#ae81ff>6</span>  <span style=color:#ae81ff>6</span> <span style=color:#ae81ff>10</span>  <span style=color:#ae81ff>7</span>  <span style=color:#ae81ff>7</span> <span style=color:#ae81ff>11</span>
</span></span><span style=display:flex><span>	  <span style=color:#ae81ff>5</span>  <span style=color:#ae81ff>5</span>  <span style=color:#ae81ff>6</span>  <span style=color:#ae81ff>1</span> <span style=color:#ae81ff>10</span> <span style=color:#ae81ff>10</span> <span style=color:#ae81ff>11</span> <span style=color:#ae81ff>11</span>
</span></span><span style=display:flex><span>	 <span style=color:#ae81ff>13</span> <span style=color:#ae81ff>13</span> <span style=color:#ae81ff>14</span>  <span style=color:#ae81ff>1</span>  <span style=color:#ae81ff>1</span> <span style=color:#ae81ff>18</span> <span style=color:#ae81ff>19</span> <span style=color:#ae81ff>19</span>
</span></span><span style=display:flex><span>	 <span style=color:#ae81ff>13</span> <span style=color:#ae81ff>12</span> <span style=color:#ae81ff>14</span> <span style=color:#ae81ff>14</span> <span style=color:#ae81ff>18</span> <span style=color:#ae81ff>18</span> <span style=color:#ae81ff>17</span> <span style=color:#ae81ff>19</span>
</span></span><span style=display:flex><span>	 <span style=color:#ae81ff>15</span> <span style=color:#ae81ff>12</span> <span style=color:#ae81ff>12</span> <span style=color:#ae81ff>16</span> <span style=color:#ae81ff>20</span> <span style=color:#ae81ff>17</span> <span style=color:#ae81ff>17</span> <span style=color:#ae81ff>21</span>
</span></span><span style=display:flex><span>	 <span style=color:#ae81ff>15</span> <span style=color:#ae81ff>15</span> <span style=color:#ae81ff>16</span> <span style=color:#ae81ff>16</span> <span style=color:#ae81ff>20</span> <span style=color:#ae81ff>20</span> <span style=color:#ae81ff>21</span> <span style=color:#ae81ff>21</span>
</span></span></code></pre></div><p>如上，上面所有的数字标签都排成了 L 形。（-1 除外，那是缺角所在的位置）。这段代码的实现过程基于算法上的归纳法基础和递归的思想。具体解释请参考挪威 Python 程序大拿 Magnus Lie Hetland 写的《Python 算法教程》一书第三章和第六章的知识。</p></div></article></main><aside><div><div><h3>LATEST POSTS</h3></div><div><ul><li><a href=/posts/2025-10-16-kubernetes-apiserver-authorization-mechanism/>Kubernetes APIServer 鉴权机制</a></li><li><a href=/posts/2025-09-30-kubernetes-apiserver-authentication-mechanism/>Kubernetes APIServer 认证机制</a></li><li><a href=/posts/2024-12-16-deploy-kubernetes-by-kubeadm/>使用 kubeadm 搭建 kubernetes 集群</a></li><li><a href=/posts/2024-09-20-how-to-code-review/>如何做code review</a></li><li><a href=/posts/2024-08-12-weakref-in-python/>Python中的弱引用</a></li></ul></div></div></aside><footer><p>Social Links:
<a href=https://github.com/vimiix><b>Github</b></a>.
<a href=https://www.douban.com/people/vimiix/><b>Douban</b></a>.
<a href=mailto:i@vimiix.com><b>Email</b></a>.<br><hr>&copy; 2017-2025
Vimiix Yao; All rights reserved.
<a href=https://beian.miit.gov.cn/>京ICP备19015214号-1</a></p><script src=https://l2dwidget.js.org/lib/L2Dwidget.min.js></script><script>L2Dwidget.init({model:{jsonPath:"https://unpkg.com/live2d-widget-model-tororo@1.0.5/assets/tororo.model.json"}})</script></footer></body></html>